#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct redblackNode
{
    int value;
    char color;
    struct redblackNode *right;
    struct redblackNode *left;
    struct redblackNode *parent; 
};
struct redblackNode *NIL;
struct redblackNode *root;
 
void left_rotate(struct redblackNode *x ) {
    struct redblackNode *y;
    y = x->right;
    x->right = y->left;
    
    if ( y->left != NIL )
        y->left->parent = x;
    y->parent = x->parent;
    
    if ( x->parent == NIL ) root = y;
    else
        if ( x == (x->parent)->left )
            x->parent->left = y;
        else
            x->parent->right = y;
    y->left = x;
    x->parent = y;
}
    
void right_rotate(struct redblackNode *x ) {
    struct redblackNode *y;
    y = x->left;
    x->left = y->right;
    if ( y->right != NIL )
        y->right->parent = x;
    y->parent = x->parent;
    
    if ( x->parent == NIL ) root = y;
    else
        if ( x == (x->parent)->right )
            x->parent->right = y;
        else
            x->parent->left = y;
    y->right = x;
    x->parent = y;
}


void fixupTree(struct redblackNode *x ) {
    struct redblackNode *y;
    //x->color = 'r';
    while ( (x != root) && (x->parent->color == 'r') ) {
       if ( x->parent == x->parent->parent->left ) {
           y = x->parent->parent->right;
           if ( y->color == 'r' ) {
               x->parent->color = 'b';             //@Case1
               y->color = 'b';                     //@Case1
               x->parent->parent->color = 'r';     //@Case1
               x = x->parent->parent;              //@Case1
               }
           else {
               if ( x == x->parent->right ) {
                   x = x->parent;                  //@Case2
                   left_rotate( x );               //@Case2
                   }
               x->parent->color = 'b';             //@Case3
               x->parent->parent->color = 'r';     //@Case3
               right_rotate(  x->parent->parent ); //@Case3
               }
           }
       else {

           y = x->parent->parent->left;
           if ( y->color == 'r' ) {
               x->parent->color = 'b';
               y->color = 'b';
               x->parent->parent->color = 'r';
               x = x->parent->parent;
           }else {
               if ( x == x->parent->left ) {
                   x = x->parent;
                   right_rotate( x );
               }
               x->parent->color = 'b';
               x->parent->parent->color = 'r';
               left_rotate(  x->parent->parent );
           }
       }
    }
    root->color = 'b';
}
    
void insert(int key) {
     struct redblackNode *y = NIL;
     struct redblackNode *x = root; 
     struct redblackNode *node;

     while (x!=NIL) {
           y=x;
           if(x->value > key)
                x = x->left;
           else
                x = x->right;
     }

     node=(struct redblackNode*)malloc(sizeof(struct redblackNode));
     node->parent = y;
     node->value = key;
     
     if(y == NIL) { 
          root = node;
     }
     else if(key <= y->value) 
     { 
          y->left=node;
     }
     else 
          y->right = node ; 
           
     node->left = NIL;
     node->right = NIL;
     node->color = 'r';
     fixupTree (node) ;    
}
    
void print (struct redblackNode *y) { 
 
     if(y->left!=NIL)
         print(y->left);
     printf("[%d,%c] " , y->value , y->color);
     if(y->right!=NIL)
         print(y->right);
}

    
    
int main () {
    NIL=(struct redblackNode*)malloc(sizeof(struct redblackNode));
    NIL->color='b';
    int i=0;
    root=NIL;
    srand(time(NULL));
    for(i=0; i<15; i++) 
          insert(rand()%50+1);
    
    printf("Root is [%d,%c] \n" , root->value , root->color);
    print(root);
    getch();
    return 0;
}
